home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / programming / assembly / clip.lha / polyclip.code / __headers__.txt
Encoding:
Text File  |  1989-10-24  |  7.3 KB  |  72 lines
  1.  
  2. The following C functions are two versions of the Liang-Barsky
  3. polygon clipping algorithm.  The first is directly from their
  4. paper in CACM (and the corrigenda that followed).  The second
  5. is slightly modified and seems to run about 6% quicker (assuming
  6. floating point hardware).
  7.  
  8. #___________cut mark
  9.  
  10. /* Liang-Barsky Polygon Clipping [CACM, Vol 26 (Nov, 1983)] *    (with corrections from [CACM (April, 1984)]) */
  11.  
  12. /*   Note that this assumes the last point == the first in the *    polygon representation the code in the article adds the *    last point in at the start of the algorithm (probably *    a better approach). */
  13.  
  14.     /* The following include brings in some macro definitions     * for accessing information about a polygon:     *     *   NPNTS()  is the number of vertices in the polygon     *            (counting first point twice)         *         *   GETPNT() accesses the specified point out of the     *              polygon.     *     *   XCOORD/YCOORD() access the x(y)-coordinate in a point     *     * Macros were used because this code must ultimately tie     *  into my wife's animation package, and I don't know     *  how she is going to represent polygons yet.     */
  15.  
  16. # include "pln.h"
  17.  
  18. # define INFINITY    (1.0e+30)
  19.  
  20.     /* add a new vertex into the output polygon */
  21.  
  22. # define add(x,y) {\                   XCOORD(GETPNT(npoly,npnt)) = x;\                   YCOORD(GETPNT(npoly,npnt)) = y;\                   ++npnt;\                  }
  23.  
  24.     /* window bounds (xleft,ybottom), (xright,ytop) */
  25. extern float wx1,wy1,  wx2,wy2;      /* The Liang-Barsky Polygon Clipping Algorithm */
  26. fclip(opoly,npoly)   PLN *opoly, *npoly;     {   register int i, npnt;   float deltax, deltay, xin,xout,  yin,yout;   float tinx,tiny,  toutx,touty,  tin1, tin2,  tout1,tout2;   float x1,y1, x2,y2;      npnt = 0;     for (i = 0; i < NPNTS(opoly)-1; ++i) {
  27.  
  28.       x1 = XCOORD(GETPNT(opoly,i));      y1 = YCOORD(GETPNT(opoly,i));      x2 = XCOORD(GETPNT(opoly,i+1));      y2 = YCOORD(GETPNT(opoly,i+1));        deltax = x2-x1;      deltay = y2-y1;        if (deltax > 0 || (deltax == 0 && x1>wx2)) { /*  points to right */         xin = wx1;         xout = wx2;         }      else {         xin = wx2;         xout = wx1;         }      if (deltay > 0 || (deltay == 0 && y1>wy2)) { /*  points up */         yin = wy1;         yout = wy2;         }      else {         yin = wy2;         yout = wy1;         }
  29.  
  30.       tinx = (deltax != 0) ? ((xin - x1)/deltax) : -INFINITY ;      tiny = (deltay != 0) ? ((yin - y1)/deltay) : -INFINITY ;         if (tinx < tiny) {    /* hits x first */         tin1 = tinx;         tin2 = tiny;         }      else            /* hits y first */         {         tin1 = tiny;         tin2 = tinx;         }
  31.  
  32.       if (1 >= tin1) {         if (0 < tin1) {            add(xin,yin);            }         if (1 >= tin2) {        if (deltax != 0) toutx = (xout-x1)/deltax;        else {               if (wx1 <= x1 && x1 <= wx2) toutx = INFINITY;               else                        toutx = -INFINITY;           }        if (deltay != 0) touty = (yout-y1)/deltay;        else {               if (wy1 <= y1 && y1 <= wy2) touty = INFINITY;               else                        touty = -INFINITY;           }
  33.  
  34.         tout1 = (toutx < touty) ? toutx : touty ;               if (0 < tin2 || 0 < tout1) {               if (tin2 <= tout1) {                  if (0 < tin2) {                     if (tinx > tiny) {                        add (xin, y1+tinx*deltay);                        }                     else {                        add (x1 + tiny*deltax, yin);                        }                     }                  if (1 > tout1) {                     if (toutx < touty) {                        add (xout, y1+toutx*deltay);                        }                     else {                        add (x1 + touty*deltax, yout);                        }                     }                  else {                     add (x2,y2);                     }                  }               else {                  if (tinx > tiny) {                     add (xin, yout);                     }                  else {                     add (xout, yin);                     }                  }               }            }         }      }
  35.  
  36.    if (npnt) {      add(XCOORD(GETPNT(npoly,0)),YCOORD(GETPNT(npoly,0)));      }   NPNTS(npoly) = npnt;   }
  37.  
  38. #___________ cut mark
  39.  
  40. /* Modified Liang-Barsky Polygon Clipping [CACM, Vol 26 (Nov, 1983)] */
  41.  
  42. /* see the comments at the start of the unmodified version for more * details. */
  43.  
  44. # include "pln.h"
  45.  
  46. # define INFINITY    (1.0e+30)
  47. # define NEARZERO    (1.0e-30)    /* 1/INFINITY */
  48.  
  49. # define add(x,y) {\                   XCOORD(GETPNT(npoly,npnt)) = x;\                   YCOORD(GETPNT(npoly,npnt)) = y;\                   ++npnt;\                  }
  50.  
  51. extern float wx1,wy1,  wx2,wy2;    /* window boundaries */
  52.  
  53. fclip(opoly,npoly)   PLN *opoly, *npoly;     {   register int i, npnt;   float deltax, deltay, xin,xout,  yin,yout;   float tinx,tiny,  toutx,touty,  tin1, tin2,  tout1,tout2;   float x1,y1, x2,y2;      npnt = 0;     for (i = 0; i < NPNTS(opoly)-1; ++i) {
  54.  
  55.       x1 = XCOORD(GETPNT(opoly,i));      y1 = YCOORD(GETPNT(opoly,i));      x2 = XCOORD(GETPNT(opoly,i+1));      y2 = YCOORD(GETPNT(opoly,i+1));        deltax = x2-x1;      if (deltax == 0) { /* bump off of the vertical */         deltax = (x1 > wx1) ? -NEARZERO : NEARZERO ;         }      deltay = y2-y1;      if (deltay == 0) { /* bump off of the horizontal */         deltay = (y1 > wy1) ? -NEARZERO : NEARZERO ;         }
  56.  
  57.       if (deltax > 0) {        /*  points to right */         xin = wx1;         xout = wx2;         }      else {         xin = wx2;         xout = wx1;         }      if (deltay > 0) {        /*  points up */         yin = wy1;         yout = wy2;         }      else {         yin = wy2;         yout = wy1;         }
  58.  
  59.       tinx = (xin - x1)/deltax;      tiny = (yin - y1)/deltay;         if (tinx < tiny) {    /* hits x first */         tin1 = tinx;         tin2 = tiny;         }      else            /* hits y first */         {         tin1 = tiny;         tin2 = tinx;         }
  60.  
  61.       if (1 >= tin1) {         if (0 < tin1) {            add(xin,yin);            }         if (1 >= tin2) {            toutx = (xout - x1)/deltax;            touty = (yout - y1)/deltay;              tout1 = (toutx < touty) ? toutx : touty ;               if (0 < tin2 || 0 < tout1) {               if (tin2 <= tout1) {                  if (0 < tin2) {                     if (tinx > tiny) {                        add (xin, y1+tinx*deltay);                        }                     else {                        add (x1 + tiny*deltax, yin);                        }                     }                  if (1 > tout1) {                     if (toutx < touty) {                        add (xout, y1+toutx*deltay);                        }                     else {                        add (x1 + touty*deltax, yout);                        }                     }                  else {                     add (x2,y2);                     }                  }               else {                  if (tinx > tiny) {                     add (xin, yout);                     }                  else {                     add (xout, yin);                     }                  }               }            }         }      }
  62.  
  63.    if (npnt) {      add(XCOORD(GETPNT(npoly,0)),YCOORD(GETPNT(npoly,0)));      }   NPNTS(npoly) = npnt;   }
  64.  
  65. #_________ cut mark
  66.  
  67.  
  68. -Steve Wampler
  69. {...}!arizona!naucse!sbw
  70.  
  71.  
  72.